package com.study.lu;

import java.util.HashMap;
import java.util.Map;

public class 爬楼梯 {
    /**
     * 假设有N个台阶，每次只能跨过一个台阶或者俩个台阶，求一共有多少种方法
     * 题解：1.先假设第一次跨过一个台阶，那么还有N-1个台阶要走
     * 2.假设第一次跨过两个台阶，那么还有N-2个台阶要走
     * 所以以此类推 很容易得到一个递归公式f(n)=f(n-1)+f(n-2)
     * 类似 斐波那契数列（这个前两项是固定的0，1 后面依次是前两项之和 0，1，2，3，5，8，13.。。）
     * 只是这个公式的终止条件是 f(2)=2 和 f(1)=1;
     * @param args
     */
    public static void main(String[] args) {
        // 通过上面的暴力递归破解
        System.out.println(bf(10));
        // 由上面暴力破解可以发现一个规律。有重复计算的过程。
        // eg: 爬10层的方法数=爬9层的方法数+爬8层的方法数
        //      爬9层的方法数=爬8层的方法数+爬7层的方法数
        // ...
        // 依次类推，等于爬8层的方法重新算了一遍，爬7层的方法算了两遍。。。
        // 所以可以在算爬8层的方法的时候缓存爬七层 6 5 层的方法数，这样就减少很多的重复步骤
        // 这里用map 存储已经求过解的方法数 k:台阶数：val:对应的解数
        Map<Integer, Integer> cacheMap = new HashMap<>(16);
        System.out.println(bfcache(10, cacheMap));
        // bfcache :还是递归思想，只是做了缓存，但是占用大量的空间用于存储中间值，map里值越多 查询效率也就可能越低下。
        // 由公式可知 f(n)=f(n-1)+f(n-2)  n的结果只跟n-1 和 n-2 相关。
        // 那么我们知道 f(2)=2 和 f(1)=1 那么就能知道 f(3) 知道f(3), 那么就知道了f(4)
        // 依次类推，那么就能知道f(n)
        // 暴力算法是人在读书时候形成的思维，这种可以说是机器的思维
        System.out.println(fromHeadToTail(10));
    }

    private static int fromHeadToTail(int 剩余台阶) {
        int n_1 = 2, n_2 = 1, n = 0;
        // f(1) f(2) 是固定项，所以从3开始循环，到所求台阶数为止
        for (int i = 3; i <= 剩余台阶; i++) {
            // f(n) =f(n-1)+f(n-2)
            n = n_1 + n_2;
            // 调换n n-1 n-2位置 用于下次计算 因为n+1的结果只跟n 和 n-1 相关。
            n_2 = n_1;
            n_1 = n;
        }
        return n;
    }

    private static int bfcache(int 剩余台阶, Map<Integer, Integer> cacheMap) {
        if (null != cacheMap.get(剩余台阶)) {
            return cacheMap.get(剩余台阶);
        }
        if (1 == 剩余台阶) {
            cacheMap.put(1, 1);
            return 1;
        }
        if (2 == 剩余台阶) {
            cacheMap.put(2, 2);
            return 2;
        }
        int bf = bfcache(剩余台阶 - 1, cacheMap);
        cacheMap.put(剩余台阶-1, bf);
        return bf + bfcache(剩余台阶 - 2, cacheMap);
    }

    private static int bf(int 剩余台阶) {
        if (1 == 剩余台阶) {
            return 1;
        }
        if (2 == 剩余台阶) {
            return 2;
        }

        return bf(剩余台阶 - 1) + bf(剩余台阶 - 2);
    }
}
